#include <iostream>
#include <vector>
#include <queue>
#include <climits> // 用于INT_MAX
#include <algorithm> // 用于max
using namespace std;

// 定义顶点的访问状态：
const int RED = 2;   // 已访问且已确定最短路径
const int GREEN = 1; // 已访问但未确定当前长度为最短
const int WHITE = 0; // 未访问

// 计算最短路径
int findAllShortestPath(int n, const vector<vector<int>>& edges, int src) {
    // dist[x]: 保存起点到 x 的最短路径长度
    vector<int> dist(n + 1, INT_MAX);
    // visit[x]表示 x 的访问状态
    vector<int> visit(n + 1, WHITE);

    // 初始时只有起点被访问到，设置路径长度为0
    visit[src] = GREEN;
    dist[src] = 0;

    // 执行Dijkstra搜索最短路径
    for (int i = 0; i < n; i++) {
        // 搜索所有的绿点，找到路径最短的一个
        int s = 0;
        for (int j = 1; j <= n; j++) {
            if (visit[j] == GREEN && dist[j] < dist[s]) {
                s = j;
            }
        }

        // 如果没有更多可访问的顶点则直接退出
        if (s == 0) break;

        // 标记 s 为当前顶点，设置访问状态为红色并开始搜索
        visit[s] = RED;

        // 枚举当前顶点 s 的邻接路径，发现新的路径并更新维护排序数组
        for (const auto& ed : edges) {
            int u = ed[0], v = ed[1], w = ed[2];

            // 当前边是 s 的邻边，且目标顶点未完成搜索（不是红色）
            if (s == u && visit[v] != RED) {
                // 计算从起点经过s到达v的路径长度
                int d = dist[s] + w;

                // 计算出一条更短的路径长度，更新路径长度及访问状态
                if (d < dist[v]) {
                    dist[v] = d;
                    visit[v] = GREEN;
                }
            }
        }
    }

    // 输出结果并返回
    int ans = -1;
    cout << "所有的顶点路径信息:" << endl;
    for (int i = 1; i <= n; i++) {
        cout << "目标顶点 " << i << " -> " << dist[i] << endl;
        ans = max(ans, dist[i]);
    }
    return ans;
}

int main() {
    vector<vector<int>> edges = {
        {1, 2, 2}, {1, 5, 8}, {1, 4, 3}, {2, 3, 5}, {3, 5, 1}, {4, 3, 2}, {4, 5, 6}
    };
    int n = 5, src = 1;
    int ans = findAllShortestPath(n, edges, src);
    cout << "搜索完毕，最远顶点路径为：" << ans << endl;
    return 0;
}